skip to main content

An official website of the United States government Here's how you know

Official websites use .gov

A .gov website belongs to an official government organization in the United States.

Secure .gov websites use HTTPS

A lock ( lock ) or https:// means you've safely connected to the .gov website. Share sensitive information only on official, secure websites.

Search for: All records

Creators/Authors contains: "Ram, Arun"

« Prev Next »

Note: When clicking on a Digital Object Identifier (DOI) number, you will be taken to an external site maintained by the publisher. Some full text articles may not yet be available without a charge during the embargo (administrative interval).
What is a DOI Number?

Some links on this page may take you to non-federal websites. Their policies may differ from this site.

Double coset Markov chains

https://doi.org/10.1017/fms.2022.106

Diaconis, Persi; Ram, Arun; Simper, Mackenzie (January 2023, Forum of Mathematics, Sigma)

Abstract Let G be a finite group. Let $H, K$ be subgroups of G and $$H \backslash G / K$$ the double coset space. If Q is a probability on G which is constant on conjugacy classes ( $$Q(s^{-1} t s) = Q(t)$$ ), then the random walk driven by Q on G projects to a Markov chain on $$H \backslash G /K$$ . This allows analysis of the lumped chain using the representation theory of G . Examples include coagulation-fragmentation processes and natural Markov chains on contingency tables. Our main example projects the random transvections walk on $$GL_n(q)$$ onto a Markov chain on $$S_n$$ via the Bruhat decomposition. The chain on $$S_n$$ has a Mallows stationary distribution and interesting mixing time behavior. The projection illuminates the combinatorics of Gaussian elimination. Along the way, we give a representation of the sum of transvections in the Hecke algebra of double cosets, which describes the Markov chain as a mixture of Metropolis chains. Some extensions and examples of double coset Markov chains with G a compact group are discussed.
more » « less
Full Text Available
Ian G. Macdonald: Works of Art; Hochschild Polytopes; Toric and Permutoric Promotion; Smirnov Words and the Delta Conjectures; The Poincaré-extended ab-Index; Colored Permutation Statistics by Conjugacy Class; Upho Lattices and Their Cores; Pattern Heights and The Minimal Power of q in a Kazhdan-Lusztig Polynomial; Rowmotion Markov Chains; Enumerating The Faces of Split Matroid Polytopes; From Higher Bruhat Orders to Steenrod Cup-i Coproducts; On The Size of Bruhat Intervals; Vines and MAT-Labeled Graphs; Configuration Spaces and Peak Representations; A determinantal Point Process Approach to Scaling and Local Limits of Random Young Tableaux; Generalized Heawood Graphs and Triangulations of Tori; The Somewhere-To-Below Shuffles in The Symmetric Group and Hecke Algebras; Dyck Combinatorics in p-Kazhdan-Lusztig Theory; A Framework Unifying Some Bijections for Graphs and Its Connection to Lawrence Polytopes; Shi Arrangements and Low Elements in Coxeter Groups; Universal Plücker Coordinates for the Wronski Map and Positivity in Real Schubert Calculus; Wilting Theory of Flow Polytopes; Character Factorisations, z-Asymmetric Partitions, and Plethysm; Inhomogeneous Particle Process Defined by Canonical Grothendieck Polynomials; Chow Rings of Matroids as Permutation Representations; Diagram Model for The Okada Algebra and Monoid; Stanley Chromatic Functions and a Conjecture in The Representation Theory of Unipotent Groups; Regular Schur Labeled Skew Shape Posets and Their 0-Hecke Modules; Acyclonestohedra; Determinant of The Distance Matrix of a Tree; Pop-Stack for Cambrian Lattices; The Characteristic Quasi-Polynomials for Exceptional Well-Generated Complex Reflection Groups; Macdonald Characters from a New Formula for Macdonald Polynomials; Antichains in The Representation Theory of Finite Lattices; On The Scaling of Random Tamari Intervals and Schnyder Woods of Random Triangulations (with an Asymptotic D-Finite Trick); Extended Schur Functions and Bases Related by Involutions; Supersolvable Posets and Fiber-Type Arrangements; Levi-Spherical Varieties and Demazure Characters; Non-Symmetric Cauchy Kernels, Demazure Measures, and LPP; Tamari Intervals and Blossoming Trees; Eulerian Polynomials for Digraphs; Framed Polytopes and Higher Categories; Poset Polytopes and Pipe Dreams: Toric Degenerations and Beyond; On The f-Vectors of Poset Associahedra; Rational Catalan Numbers for Complex Reflection Groups; Brewing Fubini-Bruhat Orders; From Geometry to Generating Functions: Rectangulations and Permutations; Growth Diagrams for Schubert RSK; A Signed e-Expansion of The Chromatic Symmetric Function and Some New e-Positive Graphs; All Kronecker Coefficients are Reduced Kronecker Coefficients; Quasipartition and Planar Quasipartition Algebras; Invariant Theory for The Face Algebra of The Braid Arrangement; The Newton Polytope of The Kronecker Product; 0-Whirling and Rowmotion Dynamics on The Chain of V's Poset; A Whitney Polynomial for Hypermaps; The Doubly Asymmetric Simple Exclusion Process, The Colored Boolean Process, and The Restricted Random Growth Model; From Coloured Permutations to Hadamard Products and Zeta Functions; Murnaghan-Type Representations of the Elliptic Hall Algebra; Plane Partitions and Rowmotion on Rectangular and Trapezoidal Posets; Projective Dimension of Weakly Chordal Graphic Arrangements; Realizing the s-Permutahedron via Flow Polytopes; Monomial Expansions for q-Whittaker and Modified Hall-Littlewood Polynomials; Extremal Weight Crystals over Affine Lie Algebras of Infinite Rank; Lascoux Polynomials and Gelfand-Zetlin Patterns; Chain Polynomials of Generalized Paving Matroids; A Galois Structure on The Orbit of Large Steps Walks in The Quadrant; Locally Invariant Vectors in Representations of Symmetric Groups; Excedance quotients, Quasisymmetric Varieties, and Temperley-Lieb algebras; Combinatorial Properties of Triangular Partitions; Asymptotics of Bounded Lecture-Hall Tableaux; Shuffle Theorems and Sandpiles; Real Matroid Schubert Varieties, Zonotopes, and Virtual Weyl Groups; Chromatic Functions, Interval Orders, and Increasing Forests; Crystals for Variations of Decomposition Tableaux; Triangular (q, t)-Schröder Polynomials and Khovanov-Rozansky Homology; qtRSK*: A Probabilistic Dual RSK Correspondence for Macdonald Polynomials; An Extended Generalization of RSK via The Combinatorics of Type A Quiver Representations; Pattern-Avoiding Polytopes and Cambrian Lattices; A Consistent Sandpile Torsor Algorithm for Regular Matroids; Asymptotics of Bivariate Algebraico-Logarithmic Generating Functions; Two-Row Set-Valued Tableaux: Catalan+k Combinatorics; Skein Relations for Punctured Surfaces; Charmed Roots and The Kroweras Complement; Fragmenting any Parallelepiped into a Signed Tiling; Ehrhart Polynomials, Hecke Series, and Affine Buildings; Cluster Algebras and Tilings for The m = 4 Amplituhedron; Quasisymmetric Expansion of Hall-Littlewood Symmetric Functions; Geometry of C-Matrices for Mutation-Infinite Quivers; Higher Specht Polynomials and Tableaux Bijections for Hessenberg Varieties; Charge Formulas for Macdonald Polynomials at t = 0 from Multiline Queues and Diagrams; Slit-Slide-Sew Bijections for Constellations and Quasiconstellations; Crystal Chute Moves on Pipe Dreams; A Regular Unimodular Triangulation of the Matroid Base Polytope; Analogues of Two Classical Pipedream Results on Bumpless Pipedreams; Asymptotic Log-Concavity of Dominant Lower Bruhat Intervals via Brunn-Minkowski Inequality; Combinatorics of Boundary Algebras; The Commutant of Divided Difference Operators, Klyachko's Genus, and the comaj Statistic; Jack Derangements; Framing Lattices and Flow Polytopes; On The Sum of The Entries in a Character Table; Vertex Models for The Product of a Schur and Demazure Polynomial; On The f-Vectors of Flow Polytopes for The Complete Graph; Counting Unicellular Maps under Cyclic Symmetries; Weak Bruhat Interval 0-Hecke Modules in Finite Type; The Monoid Representation of Upho Posets and Total Positivity; Shards for The Affine Symmetric Group; Kromatic Quasisymmetric Functions

Ram, Arun; Macdonald, Ian G; Pilaud, Vincent; Poliakova, Daria; Defant, Colin; Madhukara, Rachana; Thomas, Hugh; Iraci, Alessandro; Nadeau, Philippe; Vanden_Wyngaerd, Anna; et al (September 2024, Séminaire lotharingien de combinatoire)
Gaetz, Christian (Ed.)
Full Text Available